Wavelet transform encoding method is known as one of the methods for high-efficiency encoding of two-dimensional signals represented by image signals (for example, see Patent Document 1).
In the wavelet transform encoding method, first, wavelet transform is carried out for a two-dimensional signal. The wavelet transform is a kind of subband encoding, which carries out N-hierarchy band division by repeating subband division at the low-frequency side for band division in horizontal and vertical directions, respectively. Such kind of band division is called octave division. In the case of division up to three hierarchies, 10 subbands are available as shown in FIG. 15.
In FIG. 15, F0 to F3 are subbands of the lowest hierarchy; F4 to F6 are subbands of the hierarchy thereabove; and F7 to F9 are subbands of the highest hierarchy. Further, F1, F4, and F7 are subbands filtered through a lowpass filter in a horizontal direction and through a highpass filter in a vertical direction; F2, F5, and F8 are subbands filtered through a highpass filter in a horizontal direction and through a lowpass filter in a vertical direction; and F3, F0, and F9 are subbands filtered through a highpass filter in both horizontal and vertical directions. Further, F0 is called the lowest-frequency subband and, other than F0, F1 to F9 are called high-frequency subbands.
A wavelet transform coefficient is included in each of the subbands F0 to F9. In the present description, the wavelet transform coefficient called HL is included in such subbands as F1, F4, and F7 filtered through a lowpass filter in a horizontal direction and through a highpass filter in a vertical direction. Further, the wavelet transform coefficient called LH is included in such subbands as F2, F5, and F8 filtered through a highpass filter in a horizontal direction and through a lowpass filter in a vertical direction. Further, the wavelet transform coefficient called HH is included in such subbands as F3, F6, and F9 filtered through as highpass filter in both horizontal and vertical directions. Further, the wavelet transform coefficient called LL is included in the lowest-frequency subband F0. Furthermore, the same coordinates are assigned to the wavelet transform coefficients LH, HL, and HH of the same spatial coordinates in the multiple high-frequency subbands of the same hierarchy to be expressed, for example, as LH (i, j), HL (i, j), and HH (i, j). Therein, x represents a horizontal direction, and y represents a vertical direction; thus, the coordinates are expressed as (x, y).
When wavelet transform is carried out in the above manner, the electric power is inclined to the wavelet transform coefficient LL included in the lowest-frequency subband, and the wavelet transform coefficients LH, HL, and HH included in the high-frequency subbands become approximately zero in value. Therefore, it is possible to compress the amount of information by utilizing variable-length codes the code length of which becomes as shorter as the value gets closer to zero to encode the wavelet transform coefficients LH, HL, and HH included in the high-frequency subbands. Further, because quantizing the wavelet transform coefficients LH, HL, and HH increases the number of the wavelet transform coefficients of zero, it is possible to further highly compress the amount of information by concomitantly utilizing run length compression or encoding.
Herein, as methods for encoding the wavelet transform coefficients included in the high-frequency subbands, there are a method of respectively encoding LH, HL, and HH such as JPEG2000, and a method of collectively encoding LH, HL, and HH located spatially at the same position within the multiple subbands belonging to the same hierarchy such as shown in Patent Document 3.
On the other hand, in wavelet transform decoding, the original two-dimensional signal is restored by inputting the code string created by wavelet transform encoding, and following the procedure opposite to the encoding.
As an example of the variable-length codes the code length of which becomes as shorter as the value gets closer to zero, there is as Golomb-Rice code. The Golomb-Rice code outputs a signal value as “a unary code”+“a k-bit fixed-length code”, wherein k is an encoding parameter for giving an estimate value of the number of significant digits.
When the Golomb-Rice code is utilized for encoding, the binary number of an encoding object is divided into the low k bits and the high rest bits; the high rest bits are replaced by a unary code. For example, when the signal 00010011 (binary expression) is encoded with k=3, after the high 5 bits (00010) excluding the low 3 bits are encoded into as unary code, the low 3 hits are outputted as they are. In the case of utilizing a code of adding, a bit “1” to the bits “0” which are just the number expressed by the bit string as a unary code, in the above example, since the numerical value of the high 5 bits is 2, 2 bits of “0” terminated with the bit “1” are outputted. Together with the low 3 bits, “001011” is finally outputted as the code.
Decoding a Golomb-Rice code utilizes the same value of k utilized in the encoding to divide the binary number of a decoding object into the low k bits and the high rest bits, and restore the high rest bits to the pre-unary-code state. For example, in decoding the code “001011” encoded with k=3 of the above, example, first, the numerical value “2” is decoded from the unary code “001” and outputted as the high 5 bits “00010” and, further, the succeeding “011” is outputted as the low 3 bits. As a result, the signal 00010011 is acquired which completely matches the original signal. In this manner, the Golomb-Rice code is a kind of reversible compression codes.
The Golomb-Rice code has a shortest code length when the value k matches the significant digits of the signal value to be encoded. In the above example of the signal 00010011, because the significant digits are 5, if k=5, then the outputted code is 110011, and the code length becomes the shortest. Therefore, there is proposed an adaptive Golomb-Rice code which dynamically predicts the value k.
An example of adaptive Golomb-Rice codes is described in Patent Document 2. In the adaptive Golomb-Rice code described in Patent Document 2, the optimum value k is predicted from the statistic of the signal value d of a Golomb-Rice encoding object (in Patent Document 2, prediction error is taken as the Golomb-Rice encoding object). In particular, by accumulating the absolute values of the signal values d having appeared so far, the average number of significant digits “k” is estimated from the summation of the accumulated values “a” and the number of accumulations “n”. Further, when the number of accumulations reaches a predetermined upper limit (Reset), a resealing process is carried out to halve the accumulated value and the number of accumulations, respectively. On the other hand, in Golomb-Rice decoding, in order to acquire the same value of k as that at the encoding side, by accumulating the absolute values of the signal values d having been decoded into Golomb-Rice codes so far, the same number of significant digits “k” as utilized in the Golomb-Rice encoding is estimated from the summation of the accumulated values “a” and the number of accumulations “n”. Further, when the number of accumulations reaches to predetermined upper limit (Reset), a resealing process is carried out to halve the accumulated value and the number of accumulations, respectively.
[Patent Document 1] JP 2003-274185 A
[Patent Document 2] US 00/5764374 A
[Patent Document 3] WO 2005/081539
[Patent Document 4] JP 2001-185643 A
In the wavelet transform encoding methods as described hereinabove, it is possible to compress the amount of information by encoding with a variable-length code the wavelet transform coefficients LH, HL, and HH included in high-frequency subbands. However, the encoding parameter must be suitable for the encoding. This is because in the case of utilizing variable-length codes such as a Golomb-Rice code and the like, a good or bad method for estimating the encoding parameter k greatly affects the compression ratio.
In Patent Document 2, by accumulating the absolute values of the signal values d having appeared so far, the average number of significant digits “k” is estimated from the summation of the accumulated values “a” and the number of accumulations “n”. Because this estimation method is proposed on the premise of taking prediction error as the Golomb-Rice encoding object, it is suitable for the case of respectively encoding LH, HL, and HH. However, it is difficult to seek a suitable encoding parameter for the case of collectively encoding LH, HL, and HH located spatially at the same position within the multiple subbands belonging to the same hierarchy. The reason is that in the wavelet transform coefficients which have appeared so far, there are included a number of coefficients which are spatially far away from the encoding object wavelet transform coefficients, and/or different in kinds a LH, HL, and HH.